package Queue_and_Stack;

import java.util.LinkedList;
import java.util.Queue;

public class _43目标和 {
    public static void main(String[] args) {
        int[] n = {1,1,1,1,1};

        System.out.println(findTargetSumWays(n, 3));
    }

    //BFS
    //模拟
    //1000ms
    public static int findTargetSumWays(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int count = 0;
        if(nums.length == 1){
            if(nums[0] == target){
                count++;
            }
            if(-nums[0] == target){
                count++;
            }
            return count;
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] aftSum = new int[nums.length];
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(target >= 0){
            if(sum < target){
                return 0;
            }
        }else {
            if(-sum > target){
                return 0;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            sum -= nums[i];
            aftSum[i] = sum;
        }
        queue.offer(nums[0]);
        queue.offer(-nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                Integer poll = queue.poll();
                int p1 = poll + nums[i];
                int p2 = poll - nums[i];
                if(i == nums.length-1){
                    if(p1 == target){
                        count++;
                    }
                    if(p2 == target){
                        count++;
                    }
                }else {
                    if(target >= 0){
                        if(p1 + aftSum[i] >= target){
                            queue.offer(p1);
                        }
                        if(p2 + aftSum[i] >= target){
                            queue.offer(p2);
                        }
                    }else {
                        if(p1 - aftSum[i] <= target){
                            queue.offer(p1);
                        }
                        if(p2 - aftSum[i] <= target){
                            queue.offer(p2);
                        }
                    }
                }
            }
        }
        return count;
    }

    //官解：递归 回溯
    //O(n^2)   O(n)
    //632ms  40.1MB
    static int count = 0;
    public static int findTargetSumWays2(int[] nums, int target) {
        backtrack(nums,target,0,0);
        return count;
    }
    public static void backtrack(int[] nums,int target, int sum, int index) {
        if(index == nums.length){
            if(sum == target){
                count++;
            }
        }else {
            backtrack(nums, target, sum + nums[index], index + 1);
            backtrack(nums, target, sum - nums[index], index + 1);
        }
    }

    //官解：动态规划
    public int findTargetSumWays3(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //01背包问题
        //a背包放的数代表表达式中的正数，b背包放的数代表表达式中的负数
        //package_a - package_b = target;
        //package_a + package_b = sum;
        //联立上式可得  package_b = diff / 2;
        //那这道题就可以转化为：给定一个大小为package_b的背包，有多少种组合方式能把背包装满？ 妥妥的0-1背包。
        //所以这题就转化为了一个组合问题，并且 由于b背包是非负整数，所以 diff 必须大于0，并且是偶数，否则必定组合不出来，可以返回0;
        int diff = sum - target;
        if(diff < 0 || diff % 2 != 0){
            return 0;
        }
        int neg = diff / 2;
        int[][] dp = new int[nums.length + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= num){
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[nums.length][neg];
    }
}
